#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
const int N = 1e4 + 10;
ll a[N], b[N], f[N];

void solve()
{
	ll n, m, k;
	cin >> n >> m >> k;
	for(int i = 0;i < m; i ++ ) cin >> a[i] >> b[i];
	for(int i = 0;i < n; i ++ ) f[i] = 1e15; 
	f[0] = 0;
	for(int i = 0;i < m; i ++ )
	{
		for(int j = 0;j < n; j ++ )
		{
			int k = j;
			while(f[(k + a[i]) % n] > f[k] + b[i])
			{
				f[(k + a[i]) % n] = f[k] + b[i];
				k = (k + a[i]) % n;
			}
		}
	}
	if(f[n - k] >= 1e15) cout << "-1" << endl;
	else cout << f[n - k] << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	cin >> t;
	while(t -- ) solve();
	return 0;
}



